package com.lft.graph03.shortest_path_graph01_dijkstra;

/**
 * 图的基本操作接口
 * @param <E>
 */
public interface GraphInterface<E> {
	/**
	 * 获取顶点的个数。
	 * @return
	 */
	int getNumOfVertex();
	
	/**
	 * 插入顶点
	 * @param v
	 * @return
	 */
	boolean insertVertex(E v);
	
	/**
	 * 删除顶点
	 * @param v
	 * @return
	 */
	boolean deleteVertex(E v);
	
	/**
	 * 定位顶点的位置
	 * @param v 要查找的顶点。
	 * @return -1 未找到。其他值就是顶点的索引。
	 */
	int indexOfVertex(E v);
	
	/**
	 * 返回顶点的值
	 * @param vertexIndex
	 * @return
	 */
	E valueOfVertex(int vertexIndex);
	
	/**
	 * 插入边
	 * @param vertexIndex1 顶点1索引
	 * @param vertexIndex2 顶点2索引
	 * @param weight       权重 1表示连接。0表示不通。
	 * @return
	 */
	boolean insertEdge(int vertexIndex1, int vertexIndex2, int weight);
	
	/**
	 * 删除边
	 * @param vertexIndex1 顶点1索引
	 * @param vertexIndex2 顶点2索引
	 * @return
	 */
	boolean deleteEdge(int vertexIndex1, int vertexIndex2);
	
	/**
	 * 查找顶点1与顶点2边的权值
	 * @param vertexIndex1 顶点1索引
	 * @param vertexIndex2 顶点2索引
	 * @return
	 */
	int getEdge(int vertexIndex1, int vertexIndex2);
	
	/**
	 * 深度优先搜索遍历——基于栈实现
	 * @param vertexIndex 顶点索引
	 * @return
	 */
	String depthFirstSearchByStack(int vertexIndex);
	
	/**
	 * 深度优先搜索遍历——基于递归
	 * @param vertexIndex 顶点索引
	 * @return
	 */
	String depthFirstSearchByRecursion(int vertexIndex);
	
	/**
	 * 广度优先搜索遍历——基于队列实现
	 * @param vertexIndex 顶点索引
	 * @return
	 */
	String breadFirstSearchByQueue(int vertexIndex);
	
	/**
	 * 最短路径算法1——迪杰斯特拉算法
	 * @param vertexIndex
	 * @return
	 */
	int[] dijkstra(int vertexIndex);
	
	/**
	 * 打印图
	 */
	void displayGraph();
	
	/**
	 * 打印源点到所有顶点的最短路径
	 */
	void displayShortestPath(int vertexIndex);
}

